
\section{High Concurrencies in CSTE Problems}
\label{concurrency}

%In P2P domain, since many uploading peers may get involved simultaneously in a typical download event, 
%it gives rise to a high concurrency.
High concurrencies in CSTE planning problems are very different from
most other temporal planning problems we have seen.  
%To better understand this high concurrency in temporal expressive planning
%domains, we examine temporal dependency here.
%When solution optimality is enforced in the P2P domain, concurrencies are naturally introduced in order to reduce the overall time span.
Figure~\ref{illuActions} illustrates the temporal dependencies (Definition~\ref{def:depc}) in
several instances from different domains.  All these instances have
comparable problem sizes.  The instance of P2P domain has 90 facts
and 252 actions, and the instance of Matchlift domain~\cite{Coles08}
has 216 facts and 558 actions.  Figure~\ref{illuActions}(I) is an
instance of the Trucks domain, which is temporally simple and thus
has all actions isolated. In Figure~\ref{illuActions}(II) for the
Matchlift domain, each action has up to two actions temporally
depending on it. In Figure~\ref{illuActions}(III) for the P2P
domain, each action has up to five actions temporally depending on
it.

\begin{figure}[tp]
 \centering
\scalebox{0.7}{\includegraphics{pic_actions.eps}}
\parbox{5in}{
\caption{\label{illuActions}\small  This figure partially
illustrates temporal dependencies of actions for instances in three
domains: Trucks, Matchlift and P2P. Each node represents an action.
Each edge represents a temporal dependency between two actions.}}
\end{figure}

